Multi-stage switching networks are gaining acceptance as a means for interconnecting multiple devices within modern digital computing systems. In particular, in parallel systems it is common to use a multi-staged switching network to interconnect n system elements, where n can be several or thousands of processors or combinations of processors and other system elements. However, most state-of-the-art processors are designed to function as uniprocessors and do not implement the functions normally required to function effectively as multi-processors. The problem becomes one of how to effectively adapt uniprocessor personal computer and workstation systems to function in a multi-processor environment.
As the field of parallel processing advances, it becomes important to leverage off of existing low cost, off-the-shelf uniprocessors. This will enable cost effective and timely parallel products to be available at the marketplace. What is required to accomplish this is an efficient way to convert existing uniprocessors to function as parallel processors with minimal complexity and cost. This will enable customers to use idle processors that they already own more efficiently and to add to the parallel system in a modularly growable fashion. One important factor in allowing uniprocessors to be used as nodes of parallel processing systems is the message passing concept. Using this concept, uniprocessors communicate with each other by sending data messages from one processor to another over a high speed interconnection means. If the interconnection means is a switch network, multiple uniprocessors can communicate simultaneously at high bandwidths and low latencies. The message passing concept solves the cache coherency problem amongst the parallel uniprocessors by making each uniprocessor responsible for its own cache coherency. When a processor sends or receives a message, each processor must handle any local cache coherency operations. However, other processors can not read or write a processors local memory, but must communicate by messages, instead of shared memory techniques. Therefore, there are no global caching problems.
Message passing techniques have some problems. As the field of parallel processing advances, the need for better performing message passing means becomes of prime importance. New high performance switches and networks have made it difficult for the message passing software to keep pace, and have emphasized the bottleneck caused by the software. For instance, new high speed switches like the ALLNODE switch, as described in U.S. Ser. No. 07/677,543, are capable of passing a message in a few hundred nanoseconds, whereas the software time can range from several to 300 or more microseconds to send and receive a message. The problem posed is to find new and innovative ways to reduce the software overhead and the bottleneck it produces for message passing systems.
The message passing software problems are not as noticeable with the state-of-the-art interconnection solutions for multiple personal computers and workstations which are relative slow. The interconnection means involve serial, high-latency Token Ring and Ethernet connections, which do not provide the parallel characteristics and low-latency concepts required for modern interconnect systems. The characteristics that are required include the ability to dynamically and quickly establish and break element interconnections, to do it cheaply and easily in one chip, to have expandablity to many thousands of elements, to permit any length, non-calibrated interconnection wire lengths, to solve the distributed clocking problems and allow future frequency increases, and to permit parallel establishment and data transmittal over N switching paths simultaneously.
Amongst the most commonly used networks for digital communication between processors are the Ethernet or Token Ring LAN networks. "Ethernet: Distributed Packet Switching for Local Computer Networks" Communications of the ACM, July 1976, Vol.19, No. 7, pp 393-404; and "Token-Ring Local-Area Networks and Their Performance", W. Bux, Proceedings of the IEEE, Vol. 77, No.2, February 1989, pp 238-256; are representative articles which describe this kind of network, which provide a serial shared medium used by one node at a time to send a message to another node or nodes. The present invention is a replacement for this the Ethernet and Token-Ring networks that supports a parallel medium capable of multiple simultaneous transfers.
U.S. Pat. No. 4,803,485--LAN COMMUNICATION SYSTEM, represents one LAN approach which use of the present inventions would replace. This patent describes a medium conversion adapter similar to the present invention, but for adapting various bus protocols to a communication system having multiple transmission media segments in a ring configuration, like a token ring or LAN. The present invention differs in that it adapts multiple transmission segments in an unbuffered multi-stage parallel transfer configuration, that gets latencies in the sub-microsecond range, rather than in the millisecond range of LAN's. This differences will be of value in the future.
The distributed and fully parallel switch utilized herein to provide greatly improved interconnection properties over the Ethernet or Token Ring LAN networks is the ALLNODE Switch (Asynchronous, Low Latency, inter-NODE switch), which is disclosed in U.S. Ser. No. 07/677,543 and adapted by the present invention to perform the switching of converted bus interfaces at low latencies and high bandwidths. The ALLNODE switch provides a circuit switching capability at high bandwidths, and includes distributed switch path connection set-up and tear-down controls individually within each switch--thus providing parallel set-up, low latency, and elimination of central point failures. We will further describe in the detailed description a way whereby the ALLNODE switch and the present invention can be used to solve the bus-based processor interconnection problem effectively.